Inteligencia Artificial

1 Contenido de la clase

Satisfactibilidad: modelos, Ask y Tell [00:00-00:52]

Una base de conocimiento (KB) es un conjunto de fórmulas; el conjunto de modelos (mundos: asignaciones de valores de verdad) que la hacen verdadera se denota M(KB). La KB es satisfactible si M(KB) ≠ ∅, es decir, si existe al menos un mundo donde todas sus fórmulas son verdaderas [05:25-05:50].

M(KB) ≠ ∅ → KB es satisfactible [05:25-05:50]

Informar y preguntar por una fórmula f se reduce a un problema de satisfacción:

• Tell f (informar): distingue si "ya sabía" (KB ⊨ f), si "no lo creo" (KB ⊨ ¬f) o si "aprendí algo" (contingencia).
• Ask f (preguntar): responde sí (KB ⊨ f), no (KB ⊨ ¬f) o "no sé" (contingencia) [00:16-00:48].

¿Cómo sabemos si una fórmula es satisfactible? [05:52-06:36]

Para saber si, por ejemplo, "lluvia" es satisfactible hay que encontrar al menos un mundo: asignar verdadero o falso a cada variable y comprobar la fórmula. Por fuerza bruta hay que probar todas las combinaciones: con n variables hay 2ⁿ mundos (con dos variables, cuatro combinaciones), de modo que el problema crece exponencialmente; este es el problema de satisfactibilidad (SAT) [05:52-06:36].

Inferencia: reglas que operan sobre la sintaxis [07:11-09:05]

Ejemplo clásico: "está lloviendo" (rain); "si llueve, entonces está mojado" (rain→wet); por tanto "está mojado" (wet). En general, para símbolos proposicionales p y q:

p, p→q ⊢ q (regla del modus ponens) [07:11-08:16]

Estas reglas de inferencia operan sobre la sintaxis (manipulan símbolos, aplicando una regla tras otra) y no sobre la semántica (no evalúan tablas de verdad) [08:31-09:05]. Dos propiedades clave:

• Coherencia: si KB ⊢ f entonces KB ⊨ f — no se puede derivar algo falso.
• Completitud: si KB ⊨ f entonces KB ⊢ f — se puede derivar toda verdad [23:23-24:30].

Algoritmo de inferencia hacia adelante [09:05-09:45]

Entrada: una KB y un conjunto de reglas de inferencia. Se repite hasta que no haya cambios en la KB: elegir fórmulas f₁...fₖ ∈ KB; si existe una regla con antecedente f₁...fₖ y conclusión g, añadir g a la KB. Se dice que KB deriva f (KB ⊢ f) si f eventualmente se agrega a la KB.

Ejemplo con KB = {rain, rain→wet, wet→slippery}: se deriva wet (mojado) y después slippery (resbaloso) [20:40-21:53]. El profesor lo compara con la manipulación algebraica: de una ecuación se aplican reglas de simplificación válidas hasta llegar a la meta [09:45-20:15].

Los teoremas de incompletitud de Gödel [24:33-24:55]

Para cualquier sistema axiomático lo bastante fuerte como para describir la aritmética de los números naturales:

• Si el sistema es consistente, no puede ser completo.
• La consistencia de los axiomas no puede demostrarse dentro del propio sistema.
• Es imposible usar el método axiomático para vincular todas las verdades matemáticas [24:44-24:55].

Por eso el modus ponens es coherente pero no completo [27:10-27:24]: hace falta o bien restringir las fórmulas (cláusulas de Horn) o bien usar reglas de inferencia más poderosas (resolución).

Opción 1: cláusulas de Horn [25:40-28:45]

• Cláusula de Horn: disyunción con a lo más un literal positivo. Tres formas: definida (exactamente un positivo), de meta (cero positivos) y hecho (un positivo solo).
• Cláusula definida: p₁ ∧ … ∧ pₖ → q (ej.: Rain ∧ Cdmx → Traffic). Un hecho es el caso sin antecedente (True → q), p. ej. Rain.
• Cláusula de meta: p₁ ∧ … ∧ pₖ → false (ej.: Rain ∧ Accident → false).
• Modus ponens generalizado: p₁,…,pₖ, (p₁∧…∧pₖ)→q ⊢ q. Ejemplo: wet, weekday, wet∧weekday→traffic ⊢ traffic [28:28-28:37].

p₁,…,pₖ, (p₁∧…∧pₖ)→q ⊢ q (modus ponens generalizado) [28:24-28:37]

El modus ponens es completo para KB de cláusulas definidas (no para cualquier cláusula de Horn ni en general), y la inferencia hacia adelante corre en tiempo lineal; a cambio, Horn es menos expresivo [28:37-28:45]. Se puede reescribir con la equivalencia p→q ≡ ¬p∨q: A, A→C queda como A, ¬A∨C ⊢ C [29:16-30:00].

Opción 2: resolución y forma normal conjuntiva [40:27-47:10]

Las cláusulas generales tienen cualquier número de literales (ej.: ¬A ∨ B ∨ ¬C ∨ D). La regla de resolución cancela un par de literales complementarios:

f₁∨…∨fₙ∨p , ¬p∨g₁∨…∨gₘ ⊢ f₁∨…∨fₙ∨g₁∨…∨gₘ [40:46-41:50]

Ejemplo: rain∨snow, ¬snow∨traffic ⊢ rain∨traffic [40:46-40:54]. Para poder usarla con fórmulas cualesquiera se convierte todo a forma normal conjuntiva (CNF), una conjunción de cláusulas, con M(f) = M(f′): eliminar la doble implicación, eliminar → (f→g ≡ ¬f∨g), "empujar" negaciones (leyes de De Morgan: ¬(f∧g) ≡ ¬f∨¬g y ¬(f∨g) ≡ ¬f∧¬g), quitar la doble negación (¬¬f ≡ f) y distribuir ∨ sobre ∧ (f∨(g∧h) ≡ (f∨g)∧(f∨h)) [46:23-47:10].

Algoritmo de resolución y ejercicio [47:41-63:44]

Como KB ⊨ f equivale a que KB ∪ {¬f} sea insatisfactible: se añade ¬f a la KB, se convierte todo a CNF y se aplica la resolución repetidamente; si se deriva falso (cláusula vacía), f queda vinculada. En general esto implica tiempo exponencial [47:51-48:15].

Ejercicio con KB = {A→B∨C, A, ¬B, ¬C}:

• Resolviendo ¬A∨B∨C con A → B∨C;
• luego B∨C con ¬B → C;
• y C con ¬C → cláusula vacía: la KB es insatisfactible [61:00-63:44].

El profesor sugiere hacerlo en grupo para apreciar el resultado semántico de las operaciones sintácticas [62:57-63:07].

Limitaciones y motivación: lógica de primer orden [65:50-68:15]

Transformar lenguaje natural a lógica ("Alice y Bob saben inteligencia artificial", "todos los estudiantes saben inteligencia artificial", "cada entero par mayor que 2 es la suma de dos primos") no es posible en lógica proposicional porque solo cuenta con símbolos proposicionales: no hay objetos ni predicados, ni variables ni cuantificadores [68:09-68:15]. Eso motiva la lógica de primer orden, tema de la próxima clase [65:50-66:06].

Complementos y precisiones

• Cláusula de Horn completa: la definición correcta es "a lo más un literal positivo"; además de las definidas y de meta, los hechos (un literal positivo aislado, p. ej. Rain) también lo son.
• Alcance del modus ponens: es coherente siempre, pero completo solo para KB de cláusulas definidas; el algoritmo que lo explota es el encadenamiento hacia adelante (lineal).
• Encadenamiento hacia atrás (backward chaining): razona desde la consulta hacia los hechos; es la base de Prolog y de la programación lógica.
• Resolución refutation-complete: si KB ∪ {¬f} es insatisfactible, siempre se deriva la cláusula vacía (no enumera todas las consecuencias, pero sí refuta).
• En la práctica: como la resolución es exponencial, se usan DPLL (retroceso + propagación unitaria) y búsqueda local (WalkSAT).

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

No se indicaron tareas con fecha de entrega en esta clase. El profesor dejó prácticas recomendadas:

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

6 Glosario de términos

• Satisfactible: una fórmula o KB tiene al menos un modelo (M(KB) ≠ ∅).
• Modelo (M): asignación de valores de verdad a las variables que hace verdadera la fórmula; un "mundo".
• Base de conocimiento (KB): conjunto de fórmulas que el sistema da por verdaderas.
• Inferencia: derivar nuevas fórmulas (conclusiones) a partir de la KB mediante reglas.
• Modus ponens: regla p, p→q ⊢ q.
• Coherente (sound): regla que solo deriva fórmulas que son consecuencia lógica.
• Completo: regla que deriva toda consecuencia lógica de la KB.
• Contingencia: fórmula verdadera en unos mundos y falsa en otros (ni siempre verdadera ni siempre falsa).
• Cláusula de Horn: disyunción con a lo más un literal positivo (incluye definidas, de meta y hechos).
• Cláusula definida: p₁ ∧ … ∧ pₖ → q (exactamente un literal positivo).
• Hecho: cláusula definida sin antecedente (un único literal positivo, p. ej. Rain).
• Cláusula de meta: p₁ ∧ … ∧ pₖ → false (cero literales positivos; una consulta u objetivo).
• Encadenamiento hacia adelante / atrás: algoritmos de inferencia sobre cláusulas definidas; el segundo es la base de Prolog.
• Refutation-complete: propiedad de la resolución: si KB ∪ {¬f} es insatisfactible, siempre deriva la cláusula vacía.
• DPLL / WalkSAT: algoritmos de model checking para SAT (retroceso con propagación unitaria / búsqueda local).
• Literal: un símbolo proposicional o su negación.
• CNF (forma normal conjuntiva): conjunción de cláusulas (disyunciones de literales).
• Resolución: regla que cancela un par de literales complementarios p y ¬p entre dos cláusulas.
• Inferencia hacia adelante: algoritmo que añade conclusiones a la KB hasta que deja de cambiar.

7 Mapa mental textual

• Inteligencia Artificial · Clase 10 · Lógica proposicional
  • Satisfactibilidad y modelos
    • M(KB) ≠ ∅
    • Ask / Tell → satisfactibilidad (sí / no / contingencia)
    • Fuerza bruta: 2ⁿ mundos → problema SAT (exponencial)
  • Inferencia
    • Reglas sobre la sintaxis
    • Modus ponens: p, p→q ⊢ q
    • Coherencia y completitud
    • Gödel: consistente ⇒ incompleto
  • Opción 1: cláusulas de Horn
    • Cláusulas definidas y de meta
    • Inferencia hacia adelante (lineal)
    • Menos expresivo; modus ponens completo
  • Opción 2: resolución
    • Cancelación de literales complementarios
    • Conversión a CNF (→, negaciones, doble negación, distribuir ∨)
    • Refutación: KB ∪ {¬f} insatisfactible → falso
    • Más expresivo; tiempo exponencial
  • Limitaciones → lógica de primer orden (próxima clase)